#include "Map.cpp"

// 在图中找到一个包含所有顶点的最短路径
int visited[10];
int path[10];
int n = 0;

bool SearchAllVertexSimplePath(Graph g,int v) {
    visited[v] = true;
    path[n] = v;
    n = n+1;
    // 结束条件
    if (n == g->vexnum) {
        Display(g,path);
        return true;
    }
    ArcNode* p = g->vertex[v]->firstArc;
    while(p != NULL) {
        if (!visited[p->adj] && SearchAllVertexSimplePath(g, p->adj)) {
            return true;
        }
        p = p->next;
    }
    visited[v] = false;
    path[n] = 0;
    n = n-1;
    return false;
}

bool SearchAllVertexSimplePathMap(GraphMap g,int v) {
    visited[v] = true;
    path[n] = v;
    n = n+1;
    if (n == g->vexnum) {
        DisplayMap(g,path);
        return true;
    }
    int w = FirstAdjVertex(g,v);
    while(w != -1) {
        if (!visited[w] && SearchAllVertexSimplePathMap(g,w)) {
            return true;
        }
        w = NextAdjVertex(g,v,w);
    }
    visited[v] = false;
    n = n-1;
    return false;
}

int main() {
    Graph g = CreateGraphByFile("Map.txt");
    for (int i = 0; i <= g->vexnum; ++i) {
        visited[i] = false;
    }
    SearchAllVertexSimplePath(g,1);

    GraphMap g2 = CreateGraphMapByFile("Map.txt");
    for (int i = 0; i <= g->vexnum; ++i) {
        visited[i] = false;
    }
    n = 0;
    SearchAllVertexSimplePathMap(g2,1);
}